package com.mzy;

import com.mzy.utils.Utils;

import java.util.Arrays;

public class InsertSort {


    // public static void sort(int[] arr) {
    //     int N = arr.length;
    //     for (int i = 1; i < N; i++) {
    //         int newIndex = i;
    //         while (newIndex > 0 && arr[newIndex - 1] > arr[newIndex]) {
    //             swap(arr, newIndex - 1, newIndex);
    //             newIndex--;
    //         }
    //     }
    // }


    public static void main(String[] args) {
        Integer[] arr = {2, 1, 56, 8, 3, 7, 9, 3, 89, 6};
        sort(arr);

        System.out.println(Arrays.toString(arr));

        // Utils.testSort(InsertSort::insertSort);
    }

    private static void insertSort(Integer[] arr) {
        int n = arr.length;

        for (int i = 1; i < n; i++) {
            int newNum = arr[i];
            int newIndex = i - 1;
            while (newIndex >= 0 && newNum > arr[newIndex]) {
                arr[newIndex + 1] = arr[newIndex];
                newIndex--;
            }
        }
    }

    private static void sort(Integer[] arr) {

        int n = arr.length;

        for (int i = 1; i < n; i++) {
            int newNum = arr[i];
            int j = i - 1;

            while (j >= 0 && arr[j] > newNum) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = newNum;
        }

    }

    // private static void sort(Integer[] arr) {
    //     int n = arr.length;
    //
    //
    //     for (int i = 1; i < n; i++) {
    //         int newNum = arr[i]; // newNum 8
    //         int j = i - 1; // arr[j] 56
    //         while (j >= 0 && arr[j] > newNum) {
    //             arr[j + 1] = arr[j];
    //              j--;
    //         }
    //         arr[j + 1] = newNum;
    //     }
    //
    //     // j = 0 2 > 3
    //
    //     // 2, 1, 56, 8, 3, 7, 9, 3, 89, 6
    //     // 1  2  56  8  3  7  9  3  89  6 第一轮
    //     // 1  2  8  56  3  7  9  3  89  6 第二轮
    //     // 1  2  8  5
    //
    // }
}
